package com.zyj.test.month1.day12;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Yijia Zhang
 * @create 2024-05-18 12:20
 */
public class code0022 {
    List<String> res;
    public List<String> generateParenthesis(int n) {
        res = new ArrayList<>();
        backTrack(n, n, new StringBuilder(n));
        return res;
    }

    private void backTrack(int l, int r, StringBuilder sb) {
        if (l == 0 && r == 0) {
            res.add(sb.toString());
            return;
        }
        if (l < r) {
            sb.append(")");
            backTrack(l, r - 1, sb);
            sb.deleteCharAt(sb.length() - 1);
        }
        if (l > 0) {
            sb.append("(");
            backTrack(l - 1, r, sb);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}
